\chapter{{\color{blue}Implementaci\'on}}
\label{ch:prototipo}

A continuaci\'on presentamos un an\'alisis de la implementaci\'on desarrollada
siguiendo con el marco te\'orico descripto en el cap\'itulo
\ref{ch:minimizacion}.  El objetivo fue implementar un prototipo de soluci\'on bas\'andonos en la
utilizaci\'on de Graph Cuts asi como en la minimizaci\'on del coeficiente de
Energ\'ia. El siguiente pseudo-c\'odigo delinea el funcionamiento del prototipo.

%\lstinputlisting{codigo/prototipo.txt}

\begin{verbatim}
Creamos el grafo con los nodos representando cada voxel unidos
    de acuerdo a la configuracion de vecindario.
Para cada etiqueta a en L
    Agregamos los nodos auxiliareas al grafo de acuerdo a
        la distribucion de etiquetas actual.
    Agregamos el nodo que representa a la nueva etiqueta
        y su "etiqueta-complemento".
    Calculamos el max flow del grafo
    Obtenemos el minimum cut.
    Actualizamos los labels de los nodos
    Si esta distribucion de labels minimiza la energia anterior
        entonces se guarda como la distribucion optima.
Devolvemos la distribucion optima encontrada
\end{verbatim}

El max$-$flow se basa en el algoritmo de Ford$-$Fulkerson utilizando una
b\'usqueda de Shortest Path \cite{Thomas2001}. El objetivo fue desarrollar un
algoritmo sencillo estimando un comportamiento eficiente.

\newpage
\subsection{{\color{blue}Configuraci\'on de vecindad}}

Al armar el grafo que representa una imagen de dos dimensiones a segmentar,
presentamos dos posibles tipos de configuraci\'on sobre los ejes del grafo. El
sistema de 4 vecinos \figref{fig:simple} y el de 8 \figref{fig:completa}.

\begin{image}
    \subfigure[Sistema de 4 vecinos]{
        \label{fig:simple}
        \includegraphics[width=40mm]{im/vecindad4}}
     \subfigure[Sistema de 8 vecinos]{
        \label{fig:completa}
        \includegraphics[width=4cm]{im/vecindad8}}
 \caption{Configuraci\'on de vecindad}
 \label{fig:vecindario}
\end{image}

Para otorgar diferentes pesos a los ejes entre vecinos en diagonal u
horizontal/vertical utilizamos el concepto de distancia Euclideana
\figref{fig:euclidean}. De esta manera cuando se le asigna un peso a un eje,
este se multiplica por su distancia euclideana.

% - fig:euclidean
\insertImage{im/euclidean}{Distancia euclideana}{fig:euclidean}{40mm}

Si planteamos una configuraci\'on de vecindad para im\'agenes de tres dimensiones
se presentan algunas modificaciones. En nuestro modelo discreto una imagen de
tres dimensiones consiste en sucesivos cortes axiales teniendo presente que entre
cada par consecutivo de los mismos asumimos una distancia $\omega$ (medida en
p\'ixeles) mayor a cero. De esta manera podemos obtener la representaci\'on de el
volumen en tres dimensiones. Luego establecemos que la vecindad de cada pixel
($i,j,k)$ (siendo k el corte axial al cual pertenece) estar\'a dada por los
siguientes grupos de p\'ixeles:

\begin{itemize}
\item Por un lado se agregar\'an a la vecindad los p\'ixeles del mismo corte axial siguiendo la figura \ref{fig:completa}
\item Luego, si $k < $ cantidad de cortes axiales, agregamos a la vecindad todos los p\'ixeles del corte $k+1$ 
que corresponderian a \ref{fig:completa} y el pixel $(i,j,k+1)$. Ver \ref{fig:vecindad3D}.
\item Luego, si $k >  1$, agregamos a la vecindad todos los p\'ixeles del corte $k-1$ que corresponderian a 
\ref{fig:completa} y el pixel $(i,j,k-1)$. 
\end{itemize}

De esta manera un pixel tendr\'a a lo sumo veintiseis vecinos (nueve
pertenecientes a el corte anterior, otros nueve al corte posterior y finalmente
ocho de su mismo corte).

Para mantener la relaci\'on de los pesos en los ejes con las distancias entre
cada uno de los p\'ixeles se seguir\'a utilizando el concepto de distancia
euclideana. La unica diferencia es que ahora debido a que se agregan nuevos
vecinos tendremos un total cinco distintas distancias. Las primeras dos son
aquellas que mostramos en \ref{fig:euclidean}, luego tenemos la distancia entre
el pixel $(i,j,k)$ y el pixel $(i,j,k-1)$ o $(i,j,k+1)$ la cual es igual a
$\omega$. Luego aquellos p\'ixeles que distan a 1 de $(i,j,k-1)$ o $(i,j,k+1)$
distar\'an a $\sqrt{1 + \sqrt{\omega}}$ de $(i,j,k)$. Y finalmente aquellos
p\'ixeles que distan a $\sqrt{2}$  de $(i,j,k-1)$ o $(i,j,k+1)$ distar\'an a
$\sqrt{\sqrt{2} + \sqrt{\omega}}$ de $(i,j,k)$.

% - fig:vecindad3D
\insertImage{im/vecindad3D}{Subconjunto de vecindad de un pixel en tres
dimensiones}{fig:vecindad3D}{60mm}
